package main

import (
	"fmt"
)

/**
执行用时：8 ms, 在所有 Go 提交中击败了93.42%的用户
内存消耗：6.5 MB, 在所有 Go 提交中击败了25.33%的用户
 */
func isMatch(s string, p string) bool {

	n, m := len(s), len(p)
	s, p = " "+s, " "+p

	f := make([][]bool, n+1)
	for i := 0; i < n+1; i++ { f[i] = make([]bool, m+1) }

	f[0][0] = true
	for i := 0; i <= n; i++ {
		for j := 1; j <= m; j++ {
			if p[j] != '*' {
				f[i][j] = (s[i] == p[j] || p[j] == '?') && i > 0 && f[i - 1][j - 1]
			} else {
				f[i][j] = f[i][j - 1] || (i > 0 && f[i - 1][j])
			}
		}
	}
	return f[n][m]
}

func main() {

	fmt.Println(isMatch("aa", "a"))  // false
}
